package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.entity.TreeNodeFull;
import com.liang.leetcode.binarytree.entity.TreeNodeN;

import java.util.*;

/**
 * 层序遍历相关题目：套模板
 */
public class BiTree04_LevelOrderRelated {

    public static void main(String[] args) {

    }

    /**
     * 107.二叉树的层次遍历 II
     * 思路：先层序遍历二叉树，最后把层序遍历结果翻转
     */
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 处理当前节点
                TreeNode node = queue.poll();
                levelList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            resultList.add(levelList);
        }
        // 翻转结果列表
        Collections.reverse(resultList);
        return resultList;
    }

    /**
     * 199.二叉树的右视图
     * 思路：层序遍历二叉树的时候，只将每层的最后一个节点放入结果列表中
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 处理当前节点
                TreeNode node = queue.poll();
                // 只存储每层的最后一个节点值
                if (i == size - 1) {
                    resultList.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return resultList;
    }

    /**
     * 637.二叉树的层平均值
     * 思路：层序遍历二叉树的时候，先记录每层节点的和，再把每层节点的平均值放入结果列表中
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            double sumNum = 0;
            for (int i = 0; i < size; i++) {
                // 处理当前节点
                TreeNode node = queue.poll();
                // 每层节点求和
                sumNum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 保存每层节点的平均值
            resultList.add(sumNum / size);
        }
        return resultList;
    }

    /**
     * 429.N叉树的层序遍历
     * 思路：将节点的多个孩子全部入队
     */
    public List<List<Integer>> levelOrderNTree(TreeNodeN root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNodeN> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 处理当前节点
                TreeNodeN node = queue.poll();
                levelList.add(node.val);
                // 入队多个子节点
                List<TreeNodeN> children = node.children;
                for (TreeNodeN child : children) {
                    queue.offer(child);
                }
            }
            resultList.add(levelList);
        }
        return resultList;
    }

    /**
     * 515.在每个树行中找最大值
     * 思路：找出每层节点的最大值并入队
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 每层节点的最大值初始为最小值
            int maxNum = Integer.MIN_VALUE;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 处理当前节点
                TreeNode node = queue.poll();
                maxNum = Math.max(node.val, maxNum);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 只入队每层节点的最大值
            resultList.add(maxNum);
        }
        return resultList;
    }

    /**
     * 116.填充每个节点的下一个右侧节点指针
     * 思路：层序遍历的时候，让当前节点的 next 指向下一个节点，每层最后一个节点不用
     */
    public TreeNodeFull connect(TreeNodeFull root) {
        if (root == null) {
            return null;
        }
        // 用队列来存储每层的节点
        Queue<TreeNodeFull> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 出队栈顶元素
                TreeNodeFull curNode = queue.poll();
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
                // 最后一个节点不用设置 next，默认为 null
                if (i < size - 1) {
                    // 获取队列中的下一个节点
                    TreeNodeFull nextNode = queue.peek();
                    curNode.next = nextNode;
                }
            }
        }
        return root;
    }

}
